Many modern navigation devices collect data such as geographic location, speed and direction of travel (heading). This data may be reported to certain service and/or data providers who may use the probe data, among other purposes, to evaluate changes in the road infrastructure. The same applies to certain mobile phones and other location-aware mobile computing devices with sufficient sensor and software equipment. This type of devices may thus be referred to as probing devices or probes.
However, the time interval between successively recorded probe data points often is found to be in the order of tens of seconds. As a result, two consecutive probe points of the recorded sequence may be geographically located rather far apart from each other. If no reference geometry for roads (or commonly used paths) is available, or if the available road geometry is possibly unreliable, data analysts frequently face the problem of estimating the missing data between such distant probe data points.
Straightforward linear interpolation of the reported probe points, as currently used, does not provide sufficient accuracy for estimating positions, if large sampling intervals are used. On a curvy road, simple linear interpolation inevitably leads to over-simplified angular trajectory estimations, which include positions outside the actual road segment. Likewise, basic spline interpolation methods that only incorporate positional information of the reported probe points are likely to fail, because the physical constraints of the vehicles are ignored. Also, when estimating plausible vehicle positions between two consecutive probe points, the common principles of road design should be taken into consideration.